package com.shuang.backtracking14;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SolveNQueens {
    //全局变量保存结果
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        //定义棋盘
        char[][] chessboard = new char[n][n];
        // 初始化棋盘（先初始化为全是 '.' 后续将合适的位置变成Q）
        for (char[] c : chessboard) {
            Arrays.fill(c, '.');
        }

        //处理
        backTracking(n, 0, chessboard);

        return res;
    }

    //row 用于记录递归到第几行了
    private void backTracking(int n, int row, char[][] chessboard) {

        //终止条件 所有行都递归完了 将最后的棋盘结果数组变形后 收集到结果集合中
        if (row == n) {
            res.add(MyArrayList(chessboard));
            return;
        }

        //for循环 i代表棋盘的列数
        for (int i = 0; i < n; i++) {
            //判断棋盘是否合理 合理的话进行后续处理
            if (isValid(row, i, n, chessboard)) {
                //合理的话将棋盘此位置改为Q
                chessboard[row][i] = 'Q';
                //递归下一行
                backTracking(n, row + 1, chessboard);
                //回溯
                chessboard[row][i] = '.';
            }
        }
    }

    //收集棋盘数组到结果集合中去
    private List<String> MyArrayList(char[][] chessboard) {

        //用于二维数组每行结果的集合
        List<String> list = new ArrayList<>();

        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }

    //检查棋盘是否合法
    private boolean isValid(int row, int col, int n, char[][] chessboard){
        //检查列是否有重复的
        for (int i = 0; i < row; i++){ //相当于剪枝处理
            if (chessboard[i][col] == 'Q'){
                return false;
            }
        }

        //检查45度斜线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
            if (chessboard[i][j] == 'Q'){
                return false;
            }
        }

        //检查135度斜线
        for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++){
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }

        //都检查完了返回true
        return true;
    }
}
